package TrieTree;

/*
单词替换
在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词(derivative)。
例如，词根help，跟随着 继承词"ful"，可以形成新的单词"helpful"。
现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
你需要将句子中的所有衍生词用词根替换掉。如果衍生词有许多可以形成它的词根，则用最短的 词根 替换它。
你需要输出替换之后的句子。

示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/trie/x0cga2/
 */

import java.util.*;

public class _32单词替换 {
    public static void main(String[] args) {

        List<String> list = new ArrayList<>();
        list.add("cat");
        list.add("cbt");
        list.add("bat");
        list.add("rat");
        System.out.println(Solution.replaceWords(list, "the cattle was rattled by the battery"));

    }
    class Solution {

        public static String replaceWords(List<String> dictionary, String sentence) {
            Trie trie = new Trie();
            for (String s : dictionary) {
                trie.insert(s);
            }
            String[] strings = sentence.split(" ");
            for (int i = 0; i < strings.length; i++) {
                String search = trie.search(strings[i]);
                if (search != null) {
                    strings[i] = search;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < strings.length; i++) {
                sb.append(strings[i]);
                if (i != strings.length - 1) {
                    sb.append(" ");
                }
            }
            return sb.toString();
        }
    }

    static class Trie{
        class TrieNode{
            public Map<Character, TrieNode> children = new HashMap<>();
            public boolean isEnd;
        }
        private TrieNode root = new TrieNode();

        public Trie(){
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.children.get(c) == null) {
                    cur.children.put(c, new TrieNode());
                }
                cur = cur.children.get(c);
            }
            cur.isEnd = true;
        }

        public String search(String word) {
            TrieNode cur = root;
            StringBuilder sb = new StringBuilder();
            for (char c : word.toCharArray()) {
                if (cur.children.get(c) == null) {
                    return null;
                }
                cur = cur.children.get(c);
                sb.append(c);
                if (cur.isEnd) {
                    return sb.toString();
                }
            }
            return null;
        }
    }





}
